package linear;

import java.util.Iterator;

/**
 * 线性表
 */
public class SequenceList<T> implements Iterable<T> {
    /**
     * 存储元素数组
     */
    private T[] elements;
    /**
     * 当前长度
     */
    private int N;

    /**
     * 创建一个容量为 capacity 的 SequenceList对象
     */
    public SequenceList(int capacity) {
        elements = (T[]) new Object[capacity];
        N = 0;
    }

    /**
     * 清空线性表
     */
    public void clear() {
        N = 0;
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 元素个数
     */
    public int length() {
        return N;
    }

    /**
     * 获取一个元素
     */
    public T get(int i) {
        if (i < 0 || i > N) {
            throw new RuntimeException("当前元素不存在!");
        }
        return elements[i];
    }

    /**
     * 在线性表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i, T t) {
        if (N >= elements.length) {
//            throw new RuntimeException("线性表元素已满!");
            // 扩容
            resize(elements.length * 2);

        }
        if (i < 0 || i > N) {
            throw new RuntimeException("索引值i不合法!");
        }

        for (int j = N - 1; j >= i; j--) {
            elements[j + 1] = elements[j];
        }
        elements[i] = t;
        N++;
    }

    private void resize(int size) {
        // 记录原数组
        T[] temp = elements;
        // 创建新数组
        elements = (T[]) new Object[size];
        // 把原来的元素拷贝的新数组
        System.arraycopy(temp, 0, elements, 0, N );
    }

    /**
     * 打印当前线性表元素
     */
    public void showElements() {
        for (int i = 0; i < N; i++) {
            System.out.print(elements[i] + " ");
        }
    }

    /**
     * 在线性表中添加一个元素T
     */
    public void insert(T t) {
        if (N >= elements.length) {
//            throw new RuntimeException("线性表元素已满!");
            resize(elements.length * 2);
        }
        elements[N++] = t;
    }

    public int capacity() {
        return elements.length;
    }

    /**
     * 删除并返回线性表中的第i个元素
     */
    public T remove(int i) {
        if (i < 0 || i > N - 1) {
            throw new RuntimeException("当前要删除的元素不存在");
        }
        T result = elements[i];

        for (int index = i; index < N - 1; index++) {
            elements[index] = elements[index + 1];
        }
        N--;
        // 如果当前元素小于 1/4 则 重置容量为原来一半
        if (N < elements.length / 4 && N > 0) {
            resize(elements.length / 2);
        }


        return result;
    }

    /**
     * 返回线性表中首次出现的指定元素的索引
     */
    public int indexOf(T t) {
        if (t == null) {
            throw new RuntimeException("查找的元素不为null");
        }
        for (int i = 0; i < N; i++) {
            if (elements[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回一个自定义的迭代器
     */
    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator<T> {
        /**
         * 当前指针
         */
        private int current;

        SIterator() {
            current = 0;
        }

        @Override
        public boolean hasNext() {
            return current < N;
        }

        @Override
        public T next() {
            return elements[current++];
        }
    }


    public static void main(String[] args) {
        SequenceList<String> sl = new SequenceList<>(10);

        sl.insert("姚明");
        sl.insert("科比");
        sl.insert("麦迪");
        sl.insert(1, "詹姆斯");
        //测试获取
        String getResult = sl.get(1);
        System.out.println("索引为1的元素为:" + getResult);

        String removeResult = sl.remove(0);
        System.out.println("删除的元素为:" + removeResult);
        System.out.println("当前线性表元素:");
        for (String s : sl) {
            System.out.println(s);
        }

        System.out.println("科比的索引值:" + sl.indexOf("科比"));
        sl.clear();
        System.out.println("清空后线性表的元素个数:" + sl.length());


        System.out.println("可变线性表测试：");
        SequenceList<String> squence = new SequenceList<>(5);
//测试遍历
        squence.insert(0, "姚明");
        squence.insert(1, "科比");
        squence.insert(2, "麦迪");
        squence.insert(3, "艾佛森");
        squence.insert(4, "卡特"); // 5个元素
        System.out.println(squence.capacity());
        squence.insert(5, "aa"); // 6个元素
        System.out.println(squence.capacity());
        for (int i = 0; i < 5; i++) { // 添加5个
            squence.insert(5, "aa");
        }
        System.out.println(squence.capacity());
        for (int i = 0; i < 7; i++) {
            squence.remove(1); // 删除7个
        }
        System.out.println(squence.capacity());
        System.out.println("当前元素个数：" + squence.length());
    }


}
